"""
Problem 95: https://projecteuler.net/problem=95

The proper divisors of a number are all the divisors excluding
the number itself. For example, the proper divisors of 28 are
1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28,
we call it a perfect number.

Interestingly the sum of the proper divisors of 220 is 284 and
the sum of the proper divisors of 284 is 220, forming a chain
of two numbers. For this reason, 220 and 284 are called an
amicable pair.

Perhaps less well known are longer chains. For example,
starting with 12496, we form a chain of five numbers:

12496 -> 14288 -> 15472 -> 14536 -> 14264 (-> 12496 -> ...)

Since this chain returns to its starting point, it is called
an amicable chain.

Find the smallest member of the longest amicable chain with
no element exceeding one million.
"""

N = 1000000
SumPDivisors = {n: 1 for n in range(N+1)}
SumPDivisors[0], SumPDivisors[1] = 0, 0

for i in range(2, int(N**0.5)+1):
    SumPDivisors[i*i] += i
    for j in range(i+1, N//i):
        SumPDivisors[i*j] += (i+j)


assert SumPDivisors[12496] == 14288

print('OK!')


def solution():
    for i in range(N+1):
        try:
            nextNum = SumPDivisors[i]
        except KeyError:
            continue

        if nextNum > N or nextNum <= 1 or nextNum not in SumPDivisors:
            SumPDivisors.pop(i)
            continue

        if nextNum == i:
            SumPDivisors[i] = []  # perfect number
            continue

        res = [nextNum]
        while True:
            nextNum = SumPDivisors[nextNum]
            # print('while-loop: i, nextNum',i,nextNum)

            if isinstance(nextNum, list) or nextNum in res:
                SumPDivisors.pop(i)
                break

            if nextNum not in SumPDivisors:
                SumPDivisors.pop(i)
                for n in res:
                    SumPDivisors.pop(n)
                break

            if nextNum == i:
                SumPDivisors[i] = res
                break
            res.append(nextNum)

    # print(SumPDivisors)
    # print(SumPDivisors[12496])

    lens = 0
    res = 0
    for key,val in SumPDivisors.items():
        if lens<len(val):
            res = key
            lens = len(val)

    return res


if __name__ == "__main__":
    from doctest import testmod

    testmod()
    print(solution())
    # 14316

    '''
    {6: [], 
    28: [], 
    220: [284], 
    496: [], 
    1184: [1210], 
    2620: [2924], 
    5020: [5564], 
    6232: [6368], 
    8128: [], 
    10744: [10856], 
    12285: [14595], 
    12496: [14288, 15472, 14536, 14264], 
    14316: [19116, 31704, 47616, 83328, 177792, 295488, 629072, 589786, 294896, 358336, 418904, 366556, 274924, 275444, 243760, 376736, 381028, 285778, 152990, 122410, 97946, 48976, 45946, 22976, 22744, 19916, 17716], 
    17296: [18416], 
    63020: [76084], 
    66928: [66992], 
    67095: [71145], 
    69615: [87633], 
    79750: [88730], 
    100485: [124155], 
    122265: [139815], 
    122368: [123152], 
    141664: [153176], 
    142310: [168730], 
    171856: [176336], 
    176272: [180848], 
    185368: [203432], 
    196724: [202444], 
    280540: [365084], 
    308620: [389924], 
    319550: [430402], 
    356408: [399592], 
    437456: [455344], 
    469028: [486178], 
    503056: [514736], 
    522405: [525915], 
    600392: [669688], 
    609928: [686072], 
    624184: [691256], 
    635624: [712216], 
    643336: [652664], 
    667964: [783556], 
    726104: [796696], 
    802725: [863835], 
    879712: [901424], 
    898216: [980984]}
    '''
